package hot;

/**
 * @author lakersUp
 * @Classname
 * @Description
 * @Date 2022/3/23 10:41
 * @Version 1.0
 */
public class Hot279numSquares {
    public int numSquares(int n){
        if(n==1){
            return 1;
        }
        int[] dp=new int[n+1];
        dp[0]=0;
        for(int i=1;i<n;i++){
            dp[i]=Integer.MAX_VALUE;
            for(int j=1;j*j<=i;j++){
                dp[i]=Math.min(dp[i-j*j],dp[i]);
            }
        }
        return dp[n];
    }
}
